class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None


class BST:
    def __init__(self, li):
        self.root = None
        if li:
            for val in li:
                self.insert(val)

    def insert(self, key):  # 插入，循环插入即可创建树
        if not self.root:
            self.root = BiTreeNode(key)
        else:
            p = self.root
            while p:
                if key < p.data:  # key要存储在左子树
                    if p.lchild:  # 如果左子树有节点，往左子树走，继续看
                        p = p.lchild
                    else:  # 如果左子树是空，就插入到左孩子的位置
                        p.lchild = BiTreeNode(key)
                        break
                elif key > p.data:
                    if p.rchild:
                        p = p.rchild
                    else:
                        p.rchild = BiTreeNode(key)
                        break
                else:
                    break

    def query(self, key):  # 查询
        p = self.root
        while p:
            if key < p.data:
                p = p.lchild
            elif key > p.data:
                p = p.rchild
            else:
                return True
        return False

    def traverse(self):  # 二叉搜索树的遍历（升序序列），可以用来排序O(nlogn)
        def in_order(root):
            if root:
                in_order(root.lchild)
                print(root.data, end='')
                in_order(root.rchild)

        in_order(self.root)


tree = BST([5, 4, 6, 8, 7, 1, 9, 2, 3])
tree.traverse()
